package io.github.maojian.collection;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Random;

/**
 * @Auther: jian.mao
 * @Date: 2022/4/13 13:04
 * @Description: https://leetcode-cn.com/problems/insert-delete-getrandom-o1/
 */
public class Q380 {
    private List<Integer> list;
    private HashMap<Integer, Integer> map;
    private Random random;


    public Q380() {
        list = new ArrayList<>();
        map = new HashMap<>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        int index = list.size();
        map.put(val, index);
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        //获取删除元素的下标
        int index = map.get(val);

        //获取末尾元素last
        int  last= list.get(list.size() - 1);

        //用末尾元素替代删除的元素
        list.set(index, last);
        map.put(last, index);

        //末尾元素已经替代了待删除元素，这里需删除末尾元素
        list.remove(list.size() - 1);
        //hash表中删除待删除元素
        map.remove(val);
        return true;
    }

    public int getRandom() {
        int randomIndex = random.nextInt(list.size());
        return list.get(randomIndex);
    }

    @Test
    public void test(){
        Q380 q380 = new Q380();
        System.out.println(q380.insert(1));
        System.out.println(q380.remove(2));
        System.out.println(q380.insert(2));
        System.out.println(q380.getRandom());
        System.out.println(q380.remove(1));
        System.out.println(q380.insert(2));
        System.out.println(q380.getRandom());
    }

    @Test
    public void test01(){
        System.out.println(random.nextInt(10));
    }
}
